// 1. 两数之和： 数组nums, 数字target, 返回元素和为target 的元素位置：  一次遍历，存哈希表并查表，空间换时间：O(n)
// 49. 字母异位词分组： 字符串数组strs, 将异位词元素合并为一组返回结果: 二维字符串数组， 一次遍历，建哈希表，存表，返回结果 O(n)
// 128. 最长连续序列： 数组nums， 返回最长的连续元素长度： 一次遍历， 建哈希表，判断目标元素是否存在 O(n)

// 283. 移动零： 数组nums，将所有元素0移动至数组末尾，且所有元素相对位置不变，无额外空间，双指针原地交换 O(n) 
// 11. 盛水最多的容器： 数组nums， 代表数轴高度，围成的最大矩形面积 O(n), 双指针，无需额外空间
// 15. 三数之和： 数组nums， 和为0的三元组， 双指针 O(n2)
// h42. 接雨水： 数组nums, 代表宽度为1的矩形高度，接水面积； 双指针O(n)， 一次遍历且空间复杂度O(1)

// 3. 无重复字符串最长子串： 字符串s中无重复字符最长子串： 双指针一次遍历
// 438. 字符串中所有异位词的子串： 字符串s，p， 求s中所有p的异位词的子串的起始索引： 滑动窗口一次遍历O(m + n)

// 560. 和为k的子数组： 数组nums和整数k，统计并返回nums中和为k的子数组个数， 一次遍历，建哈希表 + 前缀和， 前缀和 + 哈希表优化 O(n)
// h239. 滑动窗口最大值： 数组nums， k， 求nums中长度为k的滑动窗口的所有最大值 优先队列O(n(log(n))), 单调队列O(n)
// h76. 最小覆盖子串: 字符串s, p; s中覆盖p的最短子串长度： O(m + n), 滑动窗口 while + for一次遍历， 复杂度计算为 m + n 

// 53. 最大子数组和： 数组nums，返回有最大和的子数组： dp | 分治 -> 线段树 O(n)
// 56. 合并区间： 二维数组n*2的二维数组 matrix， 合并所有重叠区间, 按子区间左端点排序 O(log(n)n)
// 189. 轮转数组： 数组 nums, 向右折k个元素： 原地旋转 O(n) O(1)
// 238. 除自身以外的乘积： 数组nums, 返回ans数组，每个元素为除自身之外的所有元素乘积 O(n) 两轮遍历 前后缀分解
// h41. 缺失的第一个正数： 数组nums, 返回其中没有出现的最小的正整数： O(n) O(k), 哈希表， 三轮遍历

// 矩阵置零
// 螺旋矩阵: 螺旋遍历数组
// 旋转图像： 矩阵元素旋转
// 搜索二维矩阵

// 链表： 相交， 反转，
// 二叉树
// 图

// 回溯
// 二分

// 栈
// 堆

// 贪心
// dp

// 位运算

func twoSum(nums []int, target int) []int {
	for i, x := range nums {
		for j, := i + 1; j < len(nums); j++ {
			if x + nums[j] == target {
				return []int{i, j};
			}
		}
	}
	return []int{};
}

func twoSum_(nums[]int, target int) {
	idx := map[int]int{};
	for j, x := range nums {
		if i, ok := idx[target - x]; ok {
			return []int{i, j};
		}
	}
	return []int{};
}

func main() {
	[]int nums1 = {2,7,11,15}; target = 9;
	fmt.println("%d %d", twoSum(nums1, target));
}